home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Containrs / sa / h_multimap < prev    next >
Text File  |  1996-04-09  |  4KB  |  165 lines
  1. ---------------------------> Sather 1.1 source file <--------------------------
  2. -- h_multimap.sa: Hash table based multimap
  3. -- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
  4. -- Copyright (C) 1995, International Computer Science Institute
  5. -- $Id: h_multimap.sa,v 1.3 1996/04/09 10:05:05 borisv Exp $
  6. --
  7. -- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
  8. -- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
  9. -- LICENSE contained in the file: Sather/Doc/License of the
  10. -- Sather distribution. The license is also available from ICSI,
  11. -- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
  12. -------------------------------------------------------------------
  13.  
  14. class H_MULTIMAP{K,E} < $MULTIMAP{K,E} is
  15.    -- Multimap based on the DYNAMIC_DATABUCKET_TABLE
  16.    
  17.    private include DYNAMIC_DATABUCKET_TABLE{K,H_BAG{E}} 
  18.      map_key!->ind!,n_inds->n_inds,create->create;        
  19.    -- make public
  20.    include MULTIMAP_INCL{K,E} elt!->,size->,ind!->,pair!->,
  21.      n_targets->,n_inds->;
  22.    
  23.    readonly attr total_size: INT;
  24.  
  25.    size: INT is return total_size end;
  26.    
  27.    copy: SAME
  28.       pre ~void(self)
  29.    is
  30.       res ::= map_copy;
  31.       res.total_size := total_size;
  32.       return res
  33.    end;
  34.  
  35.    aset(k:K,e:E)
  36.       pre ~void(self)
  37.    is
  38.       h ::= hash(k);
  39.       loop
  40.      b ::= bucket(h).list!;
  41.      if elt_key_eq(b.item,k) then
  42.         ssize ::= b.data.size;
  43.         b.data.insert(e);
  44.         if ssize < b.data.size then
  45.            total_size := total_size + 1
  46.         end;
  47.         return
  48.      end
  49.       end;
  50.       newset ::= #H_BAG{E};
  51.       newset.insert(e);
  52.       set_bucket(h,#DATABUCKET{K,H_BAG{E}}(k,newset,bucket(h)));
  53.       total_size := total_size + 1;
  54.       n_inds := n_inds + 1;
  55.       update_insert
  56.    end;
  57.  
  58.    n_targets(k:K): INT
  59.       pre ~void(self)
  60.    is 
  61.       loop
  62.      b ::= bucket(hash(k)).list!;
  63.      if elt_key_eq(k,b.item) then
  64.         return b.data.size
  65.      end
  66.       end;
  67.       return 0
  68.    end;
  69.  
  70.    has_ind(k:K): BOOL
  71.    -- Return true if the multi-map (dictionary) has the index "k"
  72.       pre ~void(self)
  73.    is
  74.       return n_targets(k) > 0
  75.    end;
  76.  
  77.    has(k:K,e:E): BOOL
  78.       pre ~void(self)
  79.    is
  80.       loop
  81.      b ::= bucket(hash(k)).list!;
  82.      if elt_key_eq(k,b.item) then
  83.         return b.data.has(e)
  84.      end
  85.       end;
  86.       return false
  87.    end;
  88.  
  89.    delete(k:K,e:E)
  90.    -- Delete a single occurence of the key value pair(k,e)
  91.       pre ~void(self)
  92.    is
  93.       h: INT;
  94.       b,prev: DATABUCKET{K,H_BAG{E}};
  95.  
  96.       h := hash(k);
  97.       b := bucket(h);
  98.       loop until!( void(b) );
  99.      if elt_key_eq(b.item,k) then
  100.         if b.data.has(e) then
  101.            total_size := total_size - 1;
  102.            if b.data.size > 1 then
  103.           b.data.delete(e)
  104.            else
  105.           if void(prev) then   set_bucket(h,b.next)
  106.           else  prev.next(b.next) end;
  107.           n_inds := n_inds - 1;
  108.           update_delete
  109.            end
  110.         end;
  111.         return
  112.      end;
  113.      prev := b;
  114.      b := b.next
  115.       end
  116.    end;
  117.  
  118.    delete(k:K)
  119.    -- Delete all elements associated with element "k"
  120.       pre ~void(self)
  121.    is
  122.       dummy ::= map_delete(k);
  123.       total_size := total_size - dummy.size
  124.    end;
  125.  
  126.    target!(once k:K): E
  127.    -- Return the values associated with "k"
  128.       pre ~void(self)
  129.    is
  130.       loop
  131.      b ::= bucket(hash(k)).list!;
  132.      if elt_key_eq(k,b.item) then
  133.         loop yield b.data.elt! end;
  134.         quit
  135.      end
  136.       end
  137.    end;
  138.  
  139.    elt!: E
  140.       pre ~void(self)
  141.    is
  142.       loop
  143.      b ::= bucket( 0.upto!(asize-1) );
  144.      loop
  145.         bk ::= b.list!;
  146.         loop yield bk.data.elt! end;
  147.      end
  148.       end
  149.    end;
  150.  
  151.    pair!: TUP{K,E}
  152.       pre ~void(self)
  153.    is
  154.       loop
  155.      b ::= bucket( 0.upto!(asize-1) );
  156.      loop
  157.         bk ::= b.list!;
  158.         loop yield #(b.item,bk.data.elt!) end;
  159.      end;
  160.       end;
  161.    end;
  162.  
  163. end; -- H_MULTIMAP
  164. --=============================================================================
  165.